class Solution:
    def cuttingRope(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 1
        if n == 3: return 2

        dp = [0] *(n+1)

        dp[1] = 1
        dp[2] = 2
        dp[3] = 3

        for i in range(4, n+1):
            max_val = 0
            for j in range(1, i//2+1):
                max_val = max_val if max_val>dp[j]*dp[i-j] else dp[j]*dp[i-j]
            dp[i] = max_val

        return dp[n]